UOJ Long Round 1
好难啊。。
$T1. 多线程计算$
首先要知道一个事情：$n$ 个 $[0, 1)$ 数中第 $k$ 小数期望为 $\frac{k}{n + 1}$。根据概率的基本知识，我们不考虑存在灯同时亮起的情况，那么 $n * m$ 个灯依次亮起，有 $k$ 个灯亮的期望时长为 $\frac{1}{nm + 1}$，所以现在我们要算 $k$ 个灯亮且节能的状态个数，最后乘上 $\frac{k!(nm - k)!}{(nm + 1)(nm)!}$.
每个 $(x, y)$ 独立，分别算贡献即可。现在考虑 $(x, y)$ 给 $k$ 的贡献，容斥计算：枚举全亮的行列为 $i$、$j$，贡献为 $\binom{n}{i} \binom{m}{j} \binom{i}{x} \binom{j}{y} (-1)^{i - x} (-1)^{j - y} \binom{nm - im - jn + ij}{k - im - jn + ij}$。
最后那个组合数不关键，给它拆走。剩下的看似是个二维 $FFT$，实际上完全更简单——把 $\binom{n}{i} \binom{i}{x} (-1)^{i - x}$ 计到某个数组 $h_{i, y}$ 里（枚举 $y$ 对第一维做卷积），再枚举第一维对第二维做卷积，累计到 $[im + jn - ij]$ 里即可。做 $n$ 遍长度为 $m$ 的卷积和 $m$ 遍长度为 $n$ 的卷积，$O(nmlognm)$.
upd on 2021.3.2:
学习了第一句话那个结论的证明。
方法一
先考虑最大值的期望。枚举最大值 $x$，$\int_0^1 x \cdot x^{n - 1} dx = F(1) - F(0) = \frac{1}{n + 1} 1^{n + 1} - \frac{1}{n + 1} 0^{n + 1} = \frac{1}{n + 1}$，还要再乘 $n$ 表示哪个最大。
推广：枚举第 $k$ 小值 $x$，$\int_0^1 x \cdot x^{k - 1} \cdot (1 - x)^{n - k} dx$。考虑分部积分，即 $\int_a^b uv’ dx = uv|_a^b - \int_a^b vu’ dx$。
设 $u = (1 - x)^{n - k}$, $v’ = x^k$，则 $v = \frac{1}{k + 1} x^{k + 1}$，$uv$ 在 $0$ 和 $1$ 处都为 $0$ 所以 $uv = 0$，原柿 $= \frac{n - k}{k + 1} \int_0^1 x^{k + 1}(1 - x)^{n - k - 1} dx$
设 $a_i = \int_0^1 x^i(1 - x)^{n - k} dx$，则有 $a_i = \frac{n - i}{i + 1} a_{i + 1}$，边界 $a_n = \frac{1}{n + 1}$，可得通项公式 $a_i = \frac{i!(n - i)!}{(n + 1)!}$，乘上 $n \cdot \binom{n - 1}{k - 1}$ 表示选择方案，得 $\frac{k}{n + 1}$。
其实就是 $\Beta$ 函数！
$\Gamma$ 函数：
$\Beta$ 函数（定义域是 $x > 0$, $y > 0$）：
结论：
$\Gamma(1) = 1$, $\Gamma(x) = (x - 1) \Gamma(x - 1)$, 因此 $\Gamma(x) = (x - 1)!$
$\Beta(x, y) = \frac{\Gamma(x) \Gamma(y)}{\Gamma(x + y)}$ 证……明？
这俩基本够用了
我们求的是 $\Beta(k + 1, n - k + 1)$，化简以后乘上方案数就是 $\frac{k}{n + 1}$。
方法二
引入第 $n + 1$ 个随机变量 $x$，可以认为第 $k$ 小变量的期望等于第 $n + 1$ 个变量小于等于第 $k$ 小变量的概率。考虑大小关系，共有 $k * n!$（新变量有 $k$ 个位置可插入），所以概率为 $\frac{k}{n + 1}$。